/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/factorial
   @Language: C++
   @Datetime: 19-03-28 16:49
   */

class Solution {
public:
	/**
	 * @param n: an integer
	 * @return:  the factorial of n
	 * Tip:
	 * only support n at [0,9999]
	 */
	string factorial(int n) {
		// write your code here
		vector<int> nums={1};
		for(; n; n--){
			int carry=0;
			for (int i=0; i<nums.size(); ++i){
				carry += nums[i]*n;
				nums[i] = carry%10000;
				carry /= 10000;
			}
			if (carry>0) nums.push_back(carry);
		}
		char s[nums.size()*4+1]="", *str;
		for(int i=nums.size(); i--; sprintf(s+strlen(s),"%04d",nums[i]));
		for(str=s; *str=='0'; ++str);
		return str;
	}
};
